#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=1e5+10;
int n,m,sq,q,bloc,a[MAXN],pos[MAXN],ans1[MAXN*10],ans2[MAXN*10],st[320],ed[320];
struct Query
{
	int l,r,a,b,id;
	bool operator <(const Query b)const
	{
		return l/sq==b.l/sq?r<b.r:l/sq<b.l/sq;
	}
}qu[MAXN*10];
struct DuLiu
{
	int sum1[MAXN],sum2[320],sum3[320];
	int query1(int l,int r)
	{
		int ret=0;
		if(pos[l]==pos[r])
		{
			for(int i=l;i<=r;++i)ret+=sum1[i];
			return ret;
		}
		for(int i=l;i<=ed[pos[l]];++i)ret+=sum1[i];
		for(int i=pos[l]+1;i<pos[r];++i)ret+=sum2[i];
		for(int i=st[pos[r]];i<=r;++i)ret+=sum1[i];
		return ret;
	}
	int query2(int l,int r)
	{
		int ret=0;
		if(pos[l]==pos[r])
		{
			for(int i=l;i<=r;++i)ret+=(bool)sum1[i];
			return ret;
		}
		for(int i=l;i<=ed[pos[l]];++i)ret+=(bool)sum1[i];
		for(int i=pos[l]+1;i<pos[r];++i)ret+=sum3[i];
		for(int i=st[pos[r]];i<=r;++i)ret+=(bool)sum1[i];
		return ret;
	}
	void update(int k,int x)
	{
		if(x>0)
		{
			if(!sum1[k])++sum3[pos[k]];
			++sum1[k];++sum2[pos[k]];
		}
		else
		{
			if(sum1[k]==1)--sum3[pos[k]];
			--sum1[k];--sum2[pos[k]];
		}
		return;
	}
}T1;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=read();q=read();
	sq=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=read();
	m=sqrt(n);bloc=(n-1)/m+1;
	for(int i=1;i<=n;++i)
	{
		pos[i]=(i-1)/m+1;
		if(!st[pos[i]])st[pos[i]]=i;
		ed[pos[i]]=i;
	}

	for(int i=1;i<=q;++i)qu[i].l=read(),qu[i].r=read(),qu[i].a=read(),qu[i].b=read(),qu[i].id=i;
	sort(qu+1,qu+1+q);
	int l=1,r=0;
	for(int i=1;i<=q;++i)
	{
		while(r<qu[i].r)T1.update(a[++r],1);
		while(l>qu[i].l)T1.update(a[--l],1);
		while(r>qu[i].r)T1.update(a[r--],-1);
		while(l<qu[i].l)T1.update(a[l++],-1);
		ans1[qu[i].id]=T1.query1(qu[i].a,qu[i].b);
		ans2[qu[i].id]=T1.query2(qu[i].a,qu[i].b);
	}
	for(int i=1;i<=q;++i)
		printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}
